# -*- encoding: utf-8 -*-

import sys

class MergeSort:
	'''Algoritmo de ordenação por mistura.'''

	def __init__(self, unsortedList, firstPosition, lastPosition):
		'''Construtor da classe
		É chamado o método responsável pela ordenação da lista
		@param unsortedList -> lista que vai ser ordenada
		@param firstPosition -> primeira posição da lista para ordenar
		@param lastPosition -> última posição da lista para ordenar
		'''

		self.unsortedList = unsortedList
		self.firstPosition = firstPosition
		self.lastPosition = lastPosition
		self.merge_sort(unsortedList, firstPosition, lastPosition)

	def merge_sort(self, unsortedList, firstPosition, lastPosition):
		'''Se a primeira posição for menor que a última, divide a lista ao meio
		e usa a recursividade para fazer o mesmo às duas lista originadas da divisão
		até ao fim, depois chama a função merge para voltar a juntar as listas mas já
		ordenadas.
		@param unsortedList -> lista que vai ser ordenada
		@param firstPosition -> primeira posição da lista para ordenar
		@param lastPosition -> última posição da lista para ordenar
		'''

		self.unsortedList = unsortedList
		self.firstPosition = firstPosition
		self.lastPosition = lastPosition
		if firstPosition < lastPosition:
		    splitPosition = (firstPosition + lastPosition)/2
		    self.merge_sort(unsortedList, firstPosition, splitPosition)
		    self.merge_sort(unsortedList, splitPosition + 1, lastPosition)
		    self.merge(unsortedList, firstPosition, splitPosition, lastPosition)

	def merge(self, unsortedList, firstPosition, splitPosition, lastPosition):
		'''Nesta função recebendo a lista e um ponto de divisão, são criadas duas listas
		e preenchidas com os mesmos valores da lista por ordenar, depois vão sendo comparados
		os valores entre as duas listas, os mais pequenos vão sendo colocados por ordem na lista 
		que eantes estava desordenada.
		Nas listas temporárias criadas, existe um valor máximo inteiro para que quando ordenados
		todos os valores de uma lista, continue a passar os valores da outra que serão sempre mais
		pequenos que este valor máximo.
		@param unsortedList -> lista que vai ser ordenada
		@param firstPosition -> primeira posição da lista para ordenar
		@param lastPosition -> última posição da lista para ordenar
		@param splitPosition -> posição da lista onde foi dividida
		'''

		self.unsortedList = unsortedList
		self.firstPosition = firstPosition
		self.splitPosition = splitPosition
		self.lastPosition = lastPosition
		
		list1Size = splitPosition - firstPosition + 1
		list2Size = lastPosition - splitPosition
		
		leftList = [0 for i in range(list1Size + 1)] #Cria um array com um espaço a mais que a lista 1
		rightList = [0 for j in range(list2Size + 1)] #Cria um array com um espaço a mais que a lista 2
		
		for i in range(0, list1Size): #Preenche a lista esquerda com os valores da lista 1
		    leftList[i] = unsortedList[firstPosition + i] 
		
		for j in range(0, list2Size): #Preenche a lista esquerda com os valores da lista 2
		    rightList[j] = unsortedList[splitPosition + j + 1]
		
		leftList[list1Size] = sys.maxint #Mete na última posição da lista esquerda o maior valor inteiro
		rightList[list2Size] = sys.maxint ##Mete na última posição da lista direita o maior valor inteiro
		
		leftListPosition = 0
		rightListPosition = 0
		
		for k in range(firstPosition, lastPosition + 1):
		    if leftList[leftListPosition] <= rightList[rightListPosition]:
				unsortedList[k] = leftList[leftListPosition]
				leftListPosition += 1
		    else:
				unsortedList[k] = rightList[rightListPosition]
				rightListPosition += 1